/*
 * Author: Hiawui
 * Date: 2010/12/06
 */

#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "hv_mem_pool.h"

/* Default page size, must be power of 2 */
#define UNIT_SIZE     (1<<12)

/*
 * Memory block flags
 */
#define HV_MB_FLG_1ST       1   /* indicates if the 1st block in a freeable blcok */
#define HV_MB_FLG_USED      2   /* indicates if this block is used or not */

/*
 * Align request size to be multiple of specified size, add in block header
 * szie: requested size
 * csize: chunk size
 */
#define MEM_ALIGN_BASIC(size, csize)   \
    (((size) + sizeof(hv_mp_block_t) + ((csize) - 1)) & ~((csize) - 1))

/*
 * Align request size to be multiple of memory page size, add in block header
 * mp_p: pointer to memory pool
 * size: requested size
 */
#define MEM_ALIGN_PS(mp_p, size)    \
    MEM_ALIGN_BASIC((size), (mp_p)->mp_pagesize)

/*
 * Get memory block address
 */
#define MEM_BLOCK_ADDR(fb_p) \
    ((hv_mp_block_t*)((char*)(fb_p) - sizeof(hv_mp_block_t)))

/*
 * Get free address
 */
#define FREE_ADDR(mb_p) \
    ((hv_free_block_t*)((char*)(mb_p) + sizeof(hv_mp_block_t)))

/*
 * size of free block
 */
#define FREE_SIZE(fb_p) \
    (MEM_BLOCK_ADDR((fb_p))->mb_size)

/*
 * Set value to variable that pointer point to if pointer is not null
 * p: the pointer
 * val: the value
 */
#define SET_POINTER(p, val) \
    do{ \
        if((p) != NULL) (*(p)) = (val);   \
    }while(0)

/*
 * Calculate the pages in the size, add in the block header
 */
#define PAGES_IN_SIZE(mp_p, size)   \
    (((size) + sizeof(hv_mp_block_t) + (mp_p)->mp_pagesize - 1) / (mp_p)->mp_pagesize)

/*
 * Set memory block
 */
#define SET_MEM_BLOCK(mb_p, size, next)    \
    do{ \
        (mb_p)->mb_magic0 = MB_MAGIC0;  \
        (mb_p)->mb_flag = 0;     \
        (mb_p)->mb_size = (size);   \
        (mb_p)->mb_next = (next);   \
        (mb_p)->mb_magic1 = MB_MAGIC1;  \
    }while(0)

/*
 * Test if the memory block struct is correct.
 * mb_p: pointer to a memory block
 */
#define MEM_BLOCK_VALID(mb_p)    \
    (((mb_p)->mb_magic0 == MB_MAGIC0) && ((mb_p)->mb_magic1 == MB_MAGIC1))

/*
 * Set a flag to a memory block
 */
#define SET_FLAG(mb_p, flag)  \
    ((mb_p)->mb_flag |= (flag))

/*
 * Unset a flag of memory block
 */
#define UNSET_FLAG(mb_p, flag)  \
    ((mb_p)->mb_flag &= ~(flag))

/*
 * Test if flag is set to memory block
 */
#define HAS_FLAG(mb_p, flag)   \
    ((mb_p)->mb_flag & (flag))

/*
 * Count the bits of a integer
 * size: Size of memory
 */
/*
 *  Previousely I used following function, which has the same output.
 *    int size2bits(unsigned long size)
 *    {
 *        int i = 0;
 *        while(size)
 *        {
 *            i++;
 *            size >>= 1;
 *        }
 *        return i;
 *    }
 *  Later I found size2bits is more frequently called and took many time,
 *  so I changed to use a table to speed up this function.
 *  The speed of new function is more than 5 times faster than the old function.
 */
static int size2bits(hv_msize_t size)
{
#define XTAB1(a) ((a)>=128?8:(a)>=64?7:(a)>=32?6:(a)>=16?5:(a)>=8?4:(a)>=4?3:(a)>=2?2:(a))
#define XTAB4(a) XTAB1(a+0), XTAB1(a+1), XTAB1(a+2), XTAB1(a+3)
#define XTAB16(a) XTAB4(a+0), XTAB4(a+4), XTAB4(a+8), XTAB4(a+12)

    int i = 0;
    static const int xtab[] = {
        XTAB16(0x00), XTAB16(0x10), XTAB16(0x20), XTAB16(0x30),
        XTAB16(0x40), XTAB16(0x50), XTAB16(0x60), XTAB16(0x70),
        XTAB16(0x80), XTAB16(0x90), XTAB16(0xA0), XTAB16(0xB0),
        XTAB16(0xC0), XTAB16(0xD0), XTAB16(0xE0), XTAB16(0xF0)
    };

    return size & 0xff000000?24 + xtab[size>>24]:
           size & 0x00ff0000?16 + xtab[size>>16]:
           size & 0x0000ff00?8  + xtab[size>>8]:
                                  xtab[size];
}

/*
 * Attach the free addr to free list
 * mp_p: pointer to memory pool
 * fb_p: pointer to free block
 */
static int free_pointer(hv_mpool_t* mp_p, hv_free_block_t* fb_p)
{
    int i;
    hv_mp_block_t* mb_p;
    hv_free_block_t fb_h, *p1;

    assert(mp_p != NULL && fb_p != NULL);
    mb_p = MEM_BLOCK_ADDR(fb_p);
    if(!MEM_BLOCK_VALID(mb_p))
        return HV_MP_ERR_OVERWRITE;

    if(!HAS_FLAG(mb_p, HV_MB_FLG_USED))
        return HV_MP_ERR_FREED;

    i = size2bits(mb_p->mb_size);
    assert(i >= 0 && i <= MAX_INDEX);
    /* sort the free block in descending order */
    fb_h.fb_next = mp_p->mp_free_list[i];
    p1 = &fb_h;
    while(p1->fb_next != NULL && FREE_SIZE(p1->fb_next) > FREE_SIZE(fb_p))
    {
        p1 = p1->fb_next;
    }
    fb_p->fb_next = p1->fb_next;
    p1->fb_next = fb_p;
    mp_p->mp_free_list[i] = fb_h.fb_next;

    UNSET_FLAG(mb_p, HV_MB_FLG_USED);
    return HV_MP_ERR_NONE;
}

/*
 * Split a free block
 * mp_p: pointer to memory pool structure
 * fb_p: pointer to free block
 * size: size of user requested memory
 */
static int split_free_block(hv_mpool_t* mp_p, hv_free_block_t* fb_p, hv_msize_t size)
{
    hv_mp_block_t *mb_p, *new_mb_p;
    int ret, new_size;

    assert(fb_p != NULL);
    mb_p = MEM_BLOCK_ADDR(fb_p);
    if(!MEM_BLOCK_VALID(mb_p))
    {
        return HV_MP_ERR_OVERWRITE;
    }

    size = MEM_ALIGN_BASIC(size, UNIT_SIZE);
    if(size < (mb_p->mb_size + sizeof(hv_mp_block_t)))
    {
     /* new_size = mb_p->mb_size + sizeof(hv_mp_block_t) - size - sizeof(hv_mp_block_t); */
        new_size = mb_p->mb_size - size;
        new_mb_p = (hv_mp_block_t*)((char*)mb_p + size);
        SET_MEM_BLOCK(new_mb_p, new_size, mb_p->mb_next);
        /* this is not the 1st block */
        UNSET_FLAG(new_mb_p, HV_MB_FLG_1ST);
        /* set used flag for free */
        SET_FLAG(new_mb_p, HV_MB_FLG_USED);

        mb_p->mb_size = size - sizeof(hv_mp_block_t);
        mb_p->mb_next = new_mb_p;

        ret = free_pointer(mp_p, FREE_ADDR(new_mb_p));
        if(ret != HV_MP_ERR_NONE)
            return ret;
    }
    return HV_MP_ERR_NONE;
}

/*
 * Allocate memory from memory pool
 * mp_p: memory pool
 * size: size of requested memory
 * errno_p: error code
 */
static void* get_space(hv_mpool_t* mp_p, hv_msize_t size, int* errno_p)
{
    int i;
    hv_free_block_t* free_addr = NULL;
    hv_mp_block_t* mb_p;
    int ret;

    assert(mp_p != NULL);

    SET_POINTER(errno_p, HV_MP_ERR_NONE);

    if(size < sizeof(hv_free_block_t))
        size = sizeof(hv_free_block_t);

    i = size2bits(size);
    /* size exceeded the max size */
    if(i > MAX_INDEX)
    {
        SET_POINTER(errno_p, HV_MP_ERR_TOO_BIG);
        return NULL;
    }

    /* Try to get from free list 1st */
    for(; i <= MAX_INDEX; i++)
    {
        if(mp_p->mp_free_list[i] != NULL &&
           FREE_SIZE(mp_p->mp_free_list[i]) >= size)
        {
            free_addr = mp_p->mp_free_list[i];
            mb_p = MEM_BLOCK_ADDR(free_addr);
            if(!MEM_BLOCK_VALID(mb_p))
            {
                SET_POINTER(errno_p, HV_MP_ERR_OVERWRITE);
                return NULL;
            }
            /* this block is used */
            SET_FLAG(mb_p, HV_MB_FLG_USED);
            mp_p->mp_free_list[i] = free_addr->fb_next; /* Kick off the free block from free list */
            break;
        }
    }

    if(i > MAX_INDEX) /* No avaliable free block */
    {
        hv_msize_t alloc_size = MEM_ALIGN_PS(mp_p, size);
        mb_p = (hv_mp_block_t*)malloc(alloc_size);
        if(mb_p == NULL)
        {
            SET_POINTER(errno_p, HV_MP_ERR_ALLOC);
            return NULL;
        }
        alloc_size = alloc_size - sizeof(hv_mp_block_t);    /* size of free block */
        SET_MEM_BLOCK(mb_p, alloc_size, mp_p->mp_head);
        /* this is the 1st block & used */
        SET_FLAG(mb_p, HV_MB_FLG_1ST|HV_MB_FLG_USED);
        mp_p->mp_head = mb_p;

        free_addr = FREE_ADDR(mb_p);
    }

    /* split this free block to save memory */
    ret = split_free_block(mp_p, free_addr, size);
    if(ret != HV_MP_ERR_NONE)
    {
        SET_POINTER(errno_p, ret);
        return NULL;
    }

    return (void*)free_addr;
}

/*
 * Create new memory pool
 * errno_p: error code
 */
hv_mpool_t* hv_mpool_create(int* errno_p)
{
    hv_mpool_t* mp_p;

    SET_POINTER(errno_p, HV_MP_ERR_NONE);

    mp_p = calloc(1, sizeof(hv_mpool_t));
    if(mp_p == NULL)
    {
        SET_POINTER(errno_p, HV_MP_ERR_ALLOC);
        return NULL;
    }

    mp_p->mp_pagesize = sysconf(_SC_PAGESIZE);
    if(mp_p->mp_pagesize < UNIT_SIZE || mp_p->mp_pagesize == -1)
    {
        mp_p->mp_pagesize = UNIT_SIZE;
    }

    return mp_p;
}

/*
 * Allocate memory from pool
 * mp_p: memory pool
 * size: the size to be allocated
 * errno_p: error code
 */
void* hv_mpool_alloc(hv_mpool_t* mp_p, hv_msize_t size, int* errno_p)
{
    if(mp_p == NULL)
    {
        SET_POINTER(errno_p, HV_MP_ERR_ARG_NULL);
        return NULL;
    }

    if(size == 0)
    {
        SET_POINTER(errno_p, HV_MP_ERR_NONE);
        return NULL;
    }

    return get_space(mp_p, size, errno_p);
}

/*
 * Allocate memory from pool, initialize memory to 0
 * mp_p: memory pool
 * size: size to be allocated
 * errno_p: error code
 */
void* hv_mpool_calloc(hv_mpool_t* mp_p, hv_msize_t size, int* errno_p)
{
    void* mem;
    mem = hv_mpool_alloc(mp_p, size, errno_p);
    if(errno_p != NULL && (*errno_p) == HV_MP_ERR_NONE && mem != NULL)
        memset(mem, 0, size);
    return mem;
}

/*
 * Resize the allocated memory, content is not changed by either new_size,
 * or old size lenght, whichever the less
 * mp_p: pointer to memory pool
 * addr: memory address
 * new_size: new size of the memory
 * errno_p: error code
 */
void* hv_mpool_realloc(hv_mpool_t* mp_p, void* addr, hv_msize_t new_size, int* errno_p)
{
    hv_msize_t old_size;
    hv_mp_block_t* mb_p;
    void* new_addr;
    int ret;

    if(mp_p == NULL)
    {
        SET_POINTER(errno_p, HV_MP_ERR_ARG_NULL);
        return NULL;
    }

    mb_p = MEM_BLOCK_ADDR(addr);
    if(!MEM_BLOCK_VALID(mb_p))  /* invalid block */
    {
        SET_POINTER(errno_p, HV_MP_ERR_OVERWRITE);
        return NULL;
    }
    if(!HAS_FLAG(mb_p, HV_MB_FLG_USED)) /* block is freed */
    {
        SET_POINTER(errno_p, HV_MP_ERR_FREED);
        return NULL;
    }

    old_size = mb_p->mb_size;

    /* if new_size = 0, then behave like free() */
    if(new_size == 0)
    {
        SET_POINTER(errno_p, free_pointer(mp_p, addr));
        return NULL;
    }

    /* Original block has enough free memory for new size */
    if(old_size >= new_size)
    {
        ret = split_free_block(mp_p, addr, new_size);
        if(ret != HV_MP_ERR_NONE)
        {
            SET_POINTER(errno_p, ret);
            return NULL;
        }
        SET_POINTER(errno_p, HV_MP_ERR_NONE);
        return addr;
    }

    new_addr = get_space(mp_p, new_size, errno_p);
    if(errno_p != NULL && *errno_p != HV_MP_ERR_NONE)
    {
        return NULL;
    }

    memcpy(new_addr, addr, old_size);

    SET_POINTER(errno_p, free_pointer(mp_p, addr));
    return new_addr;
}

/*
 * Free the addr to pool
 * mp_p: pointer to memory pool
 * addr: address to be freed
 * errno_p: error code
 */
void hv_mpool_free(hv_mpool_t* mp_p, void* addr, int* errno_p)
{
    hv_mp_block_t* mb_p;
    hv_free_block_t* fb_p;

    if(mp_p == NULL)
    {
        SET_POINTER(errno_p, HV_MP_ERR_ARG_NULL);
        return;
    }
    if(addr == NULL)
    {
        SET_POINTER(errno_p, HV_MP_ERR_NONE);
        return;
    }

    fb_p = (hv_free_block_t*)addr;
    mb_p = MEM_BLOCK_ADDR(fb_p);
    if(!MEM_BLOCK_VALID(mb_p))
    {
        SET_POINTER(errno_p, HV_MP_ERR_OVERWRITE);
        return;
    }
    SET_POINTER(errno_p, free_pointer(mp_p, fb_p));
    return;
}

/*
 * find next main memory block which can be passed to free() to release the memory
 * mb_p: pointer to memory block
 * errno_p: error code
 */
static hv_mp_block_t* next_main_block(hv_mp_block_t* mb_p, int* errno_p)
{
    assert(mb_p != NULL);

    do{
        if(!MEM_BLOCK_VALID(mb_p))
        {
            SET_POINTER(errno_p, HV_MP_ERR_OVERWRITE);
            return NULL;
        }
        mb_p = mb_p->mb_next;
    }while(mb_p != NULL && !HAS_FLAG(mb_p, HV_MB_FLG_1ST));

    if(mb_p != NULL && !MEM_BLOCK_VALID(mb_p))
    {
        SET_POINTER(errno_p, HV_MP_ERR_OVERWRITE);
        return NULL;
    }

    SET_POINTER(errno_p, HV_MP_ERR_NONE);
    return mb_p;
}

/*
 * Release all memory to OS, destroy the memory pool
 * mp_p: pointer to memory pool
 * errno_p: error code
 */
void hv_mpool_destroy(hv_mpool_t* mp_p, int* errno_p)
{
    hv_mp_block_t* mb_p;

    if(mp_p == NULL)
    {
        SET_POINTER(errno_p, HV_MP_ERR_ARG_NULL);
        return;
    }

    if(mp_p->mp_head == NULL)
    {
        free(mp_p);
        SET_POINTER(errno_p, HV_MP_ERR_NONE);
        return;
    }

    if(!HAS_FLAG(mp_p->mp_head, HV_MB_FLG_1ST))
    {
        SET_POINTER(errno_p, HV_MP_ERR_BLOCK);
        return;
    }

    do{
        mb_p = mp_p->mp_head;
        mp_p->mp_head = next_main_block(mp_p->mp_head, errno_p);
        if(errno_p != NULL && *errno_p != HV_MP_ERR_NONE)
            return;
        free(mb_p);
    }while(mp_p->mp_head != NULL);

    free(mp_p);
    SET_POINTER(errno_p, HV_MP_ERR_NONE);
    return;
}

/*
 * Return error message of error code
 */
const char* hv_mpool_strerr(const int e)
{
    switch(e)
    {
    case HV_MP_ERR_NONE:
        return "no error";
        break;
    case HV_MP_ERR_ALLOC:
        return "system alloc error";
        break;
    case HV_MP_ERR_ARG_NULL:
        return "argument is null";
        break;
    case HV_MP_ERR_TOO_BIG:
        return "exceed the maximum size";
        break;
    case HV_MP_ERR_OVERWRITE:
        return "memory block structure is overwriten";
        break;
    case HV_MP_ERR_BLOCK:
        return "memory block error";
        break;
    case HV_MP_ERR_FREED:
        return "memory had been freed";
        break;
    default:
        return "unknown error";
        break;
    }
    return "unknown error";
}
